//按奇偶排序数组 II
/*给定一个非负整数数组 nums，  nums 中一半整数是 奇数 ，一半整数是 偶数 。

对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。

你可以返回 任何满足上述条件的数组作为答案 。*/
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int slow = 0;
        int quick = 0;
        while (quick < nums.size()) {
            if (nums[quick] % 2 == 0) {
                swap(nums[quick], nums[slow]);
                slow++;
            }
            quick++;
        }
        for (int i = 1; i < nums.size() / 2; i += 2) {
            if ((nums.size() / 2) % 2)
                swap(nums[i], nums[i + nums.size() / 2]);
            else
                swap(nums[i], nums[i + nums.size() / 2 - 1]);
        }
        return nums;
    }
};



//连续子数组的最大和
/*输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。*/
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型vector
     * @return int整型
     */
    int FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        int quick = 0;
        int sum = -100;
        int count = 0;
        while (quick < array.size()) {
            count += array[quick];
            sum = max(count, sum);
            if (count < 0) {
                count = 0;
            }
            quick++;
        }
        return sum;
    }
};